package leetcode.code0729;

public class MyCalendar {

	class Node {

		private int begin;
		private int end;
		private int mid;
		private boolean book;
		private Boolean bkCache;
		private Node left;
		private Node right;

		public Node(int begin, int end) {
			this.begin = begin;
			this.end = end;
			this.mid = ((end - begin) >> 1) + begin;
		}

		public Node getLeft() {
			if (this.left == null) {
				this.left = new Node(this.begin, this.mid);
			}
			return this.left;
		}

		public Node getRight() {
			if (this.right == null) {
				this.right = new Node(this.mid + 1, this.end);
			}
			return this.right;
		}

		public void book(int l, int r) {
			if (l == this.begin && r == this.end) {
				this.book = true;
				this.bkCache = true;
				return;
			}
			this.pushDown();
			if (r <= this.mid) {
				this.getLeft().book(l, r);
			} else if (l > this.mid) {
				this.getRight().book(l, r);
			} else {
				this.getLeft().book(l, this.mid);
				this.getRight().book(this.mid + 1, r);
			}
			this.book = this.getLeft().book || this.getRight().book;
		}

		public boolean isBook(int l, int r) {
			if (l == this.begin && r == this.end) {
				return this.book;
			}
			this.pushDown();
			boolean ans;
			if (r <= this.mid) {
				ans = this.getLeft().isBook(l, r);
			} else if (l > this.mid) {
				ans = this.getRight().isBook(l, r);
			} else {
				ans = this.getLeft().isBook(l, this.mid);
				ans |= this.getRight().isBook(this.mid + 1, r);
			}
			this.book = this.getLeft().book || this.getRight().book;
			return ans;
		}

		private void pushDown() {
			if (this.bkCache != null) {
				Node l = this.getLeft();
				l.book = this.book;
				l.bkCache = this.bkCache;
				Node r = this.getRight();
				r.book = this.book;
				r.bkCache = this.bkCache;
				this.bkCache = null;
			}
		}

	}

	private Node root;

	public MyCalendar() {
		root = new Node(0, (int) 1e9);
	}

	public boolean book(int start, int end) {
		if (root.isBook(start, end - 1)) {
			return false;
		}
		root.book(start, end - 1);
		return true;
	}

	public static void main(String[] args) {
		MyCalendar myCalendar = new MyCalendar();
		boolean b1, b2, b3;
		b1 = myCalendar.book(10, 20); // return True
		b2 = myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
		b3 = myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。
		System.out.println(b1 + " " + b2 + " " + b3);
	}

}
